/**
 * 2016年9月26日
 */
package algorithm.CIG;

/**
 * @author Alex
 *
 */
import java.util.ArrayList;
public class FindKSmall {
	public static void main(String arg[]){
		FindKSmall f = new FindKSmall();
		for(Integer i:f.GetLeastNumbers_Solution(new int[]{4,5,1,6,2,7,3,8}, 4)){
			System.out.println(i);
		};
	}
	 int heap[] = null;
	    
	    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
	      	ArrayList<Integer> l = new ArrayList<Integer>();
	        buildHeap(input);
	        int end = heap.length-1;
	        for(int j=k;j>0;j--){
	            l.add(heap[0]);
	            swap(heap,0,end);
	            end--;
	            adjustHeap(0, end);
	          
	        }
	        return l;
	    }
	    
	    public void buildHeap(int arr[]){
	         heap= new int[arr.length];
	        for(int i=0;i<arr.length;i++){
	            heap[i]=arr[i];
	        }
	        
	        //小根堆
	        for(int i=heap.length-1;i>=0;i--){
	            int j = i;
	            int parent = (j-1)/2;
	            while(parent>=0 && heap[parent]>heap[j]){
					swap(heap,parent,j);
	                j = parent;
	                parent = (j-1)/2;
	            }
	        }
	        
	        
	    }
	    void adjustHeap(int start,int end){
	  
	            int j = start;
	            int lc = j*2+1;
	            int rc = j*2+2;
	            while( lc<=end || rc<=end){
	            	int smaller = -1;
	            	if(lc>end){
	            		smaller = rc;
	            	}
	            	if(rc>end){
	            		smaller = lc;
	            	}
	            	if(lc<=end && rc<=end){
	            		smaller = heap[lc]<heap[rc]?lc:rc;
	            	}
	            	if(heap[j]>heap[smaller]){
	            		swap(heap,j,smaller);
	            	}
	            	j = smaller;
	            	lc=j*2+1;
	            	rc=j*2+2;
	            }
	           
	       }
	    
	    
	 	void swap(int arr[],int left,int right){
	        int temp  = arr[left];
	        arr[left] = arr[right];
	        arr[right] = temp;
	    }   
	    
}
